class Solution5 {
    public int numSquares(int n) {
          int v = (int) Math.sqrt(n) ; 
          int[] dp = new int[n+1] ; 
          for(int i=1 ; i<=n  ; i ++) dp[i] = n+1 ;

            for(int i=1 ; i<= v ; i ++){
              for(int j=1 ; j<=n ; j ++){
                 if(j>= i*i){
                    dp[j] = Math.min(dp[j] , dp[j-i*i]+1) ; 
                 }
              }
            }
          return dp[n] ;
    }
}